import functools


class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        m = len(matrix)
        n = len(matrix[0])

        @functools.cache
        def search(i, j):
            now_max = 1
            for ux, uy in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if 0 <= ux < m and 0 <= uy < n and matrix[ux][uy] > matrix[i][j]:
                    now_max = max(now_max, search(ux, uy) + 1)
            return now_max

        now_max = 1
        for i in range(m):
            for j in range(n):
                now_max = max(now_max, search(i, j))
        return now_max


data = Solution()
matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
print(data.longestIncreasingPath(matrix))
